\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{itemize}
\item
  求解方程 \(x^2 \equiv N(\bmod ~p)\)
\item
  若有解，则按 \(\bmod~p\) 后递增的顺序输出在\(\bmod~ p\)
  意义下的全部解.
\item
  若两解相同，只输出其中一个
\item
  若无解，则输出\texttt{Hola!}
\end{itemize}

\begin{lstlisting}
#define ll long long
ll w;
struct num
{
	ll x, y;
};
num mul(num a, num b, ll p)
{
	num ans = {0, 0};
	ans.x = ((a.x * b.x % p + a.y * b.y % p * w % p) % p + p) % p;
	ans.y = ((a.x * b.y % p + a.y * b.x % p) % p + p) % p;
	return ans;
}
ll powwR(ll a, ll b, ll p)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = 1ll * ans % p * a % p;
		a = a % p * a % p;
		b >>= 1;
	}
	return ans % p;
}
ll powwi(num a, ll b, ll p)
{
	num ans = {1, 0};
	while (b)
	{
		if (b & 1)
			ans = mul(ans, a, p);
		a = mul(a, a, p);
		b >>= 1;
	}
	return ans.x % p;
}
ll M_sqrt(ll n, ll p)
{
	n %= p;
	if (p == 2)
		return n;
	if (powwR(n, (p - 1) / 2, p) == p - 1)
		return -1; //不存在
	ll a;
	while (1)
	{
		a = rand() % p;
		w = ((a * a % p - n) % p + p) % p;
		if (powwR(w, (p - 1) / 2, p) == p - 1)
			break;
	}
	num x = {a, 1};
	return powwi(x, (p + 1) / 2, p);
}
signed main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while(t --)
	{
		ll n , p;
		cin >> n >> p ;
		if(!n)
		{
			cout << 0 << '\n' ; 
			continue ;
		}
		ll ans1 = M_sqrt(n , p) , ans2;
		if(ans1 == -1) cout << "Hola!\n";
		else
		{
			ans2 = p - ans1;
			if(ans1 > ans2)	swap(ans1 , ans2);
			if(ans1 == ans2) cout << ans1 << '\n'; 
			else cout << ans1 << " " << ans2 << '\n' ;
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
